Classificazione Lineare

Dopo la regressione, la classificazione è il secondo grande compito dell’apprendimento supervisionato: il target non è più un numero continuo ma una classe, cioè un’etichetta scelta in un insieme finito. Anche qui, e per le stesse ragioni viste nella regressione, si parte dai modelli lineari: semplici, interpretabili, con una teoria pulita, e mattoni fondamentali per i metodi più avanzati (le reti neurali nascono letteralmente dal perceptron che si studia in questo capitolo). Il percorso segue una progressione di ambizione crescente: prima si studia la geometria delle decision surface (superficie di decisione) lineari, poi gli approcci diretti che cercano solo la funzione di decisione (least squares (minimi quadrati) e perceptron), poi l’approccio discriminativo probabilistico che modella la probabilità della classe dato l’input (logistic regression), infine l’approccio generativo che modella la distribuzione completa dei dati (Naive Bayes). Il capitolo si chiude con un metodo non parametrico (K-Nearest Neighbors), gli strumenti di valutazione di un classificatore, i criteri per scegliere tra i vari approcci e una serie di esercizi svolti in stile esame.

Riferimenti sul testo: Bishop, Pattern Recognition and Machine Learning, capitolo 4 (4.1.1, 4.1.2, 4.1.3, 4.1.7, 4.3.1, 4.3.2).

1. Il problema della classificazione#

1.1 Definizione e ingredienti#

Il punto di partenza è identico a quello della regressione: esiste una funzione ignota che genera i dati, e la si vuole approssimare a partire da un insieme finito di osservazioni. Cambia la natura dell’output.

L’esempio guida di tutto il capitolo è il dataset Iris: per ogni fiore si misurano quattro variabili continue (lunghezza e larghezza di sepalo e petalo) e si registra la specie, che può essere setosa, versicolor o virginica. Predire la specie dalle misure è un problema di classificazione a tre classi; restringendosi alla domanda “il fiore è una setosa oppure no?” si ottiene un problema a due classi. Quando le classi sono due si parla di classificazione binaria; con $K \geq 3$ si parla di classificazione multiclasse. La distinzione non è pignoleria: alcuni metodi nascono binari e vanno estesi al multiclasse con costruzioni apposite, altri gestiscono più classi in modo nativo.

Per costruire un algoritmo di classificazione servono le solite tre risposte (come modellare $f$, come valutare l’approssimazione, come ottimizzarla) più una quarta, nuova rispetto alla regressione: come codificare la classe $C_k$. Il motivo è che i modelli sono funzioni matematiche, e una funzione matematica produce numeri; ma una classe è un concetto (un tipo di fiore, un colore, una diagnosi), non un numero. Serve quindi una convenzione che traduca il concetto in una quantità numerica su cui il modello possa lavorare, e la scelta di questa convenzione interagisce con la scelta del modello.

In parole semplici: in regressione il modello deve indovinare un numero, e i numeri le funzioni li sanno produrre naturalmente. In classificazione deve indovinare un’etichetta, e per farlo bisogna prima mettersi d’accordo su come scrivere le etichette in forma numerica. È un passo in più, apparentemente banale, che condiziona tutto il resto.

1.2 La codifica delle classi#

Per i problemi a due classi le convenzioni standard sono due:

• Codifica binaria $t \in \{0, 1\}$: $t = 1$ codifica la classe positiva, $t = 0$ la negativa. Con questa codifica sia il target sia l’output del modello si possono interpretare come probabilità della classe positiva: è la scelta naturale per gli approcci probabilistici come la logistic regression.
• Codifica $t \in \{-1, +1\}$: matematicamente equivalente, ma più comoda per alcuni algoritmi; per il perceptron, in particolare, rende le formule molto più compatte.

Per i problemi a $K$ classi verrebbe spontaneo usare un intero da $0$ a $K-1$, ma è una cattiva idea: costringerebbe il modello ad apprendere una funzione che produce esattamente quei numeri, e introdurrebbe un ordine fittizio tra le classi (come se la classe 2 fosse “a metà strada” tra la 1 e la 3). La scelta standard è un’altra.

Con questa codifica il target (e l’output del modello) si può leggere come una distribuzione di probabilità sulle classi, e il problema multiclasse si decompone naturalmente: ogni posizione del vettore è una proprietà binaria (“è di questa classe sì o no”), quindi si può imparare una funzione per ciascuna posizione.

In parole semplici: invece di dire “classe numero 4”, si accende una lampadina su un pannello di $K$ lampadine. Nessuna classe è più grande o più vicina di un’altra: tutte le codifiche sono alla stessa distanza tra loro, e il modello può trattare ogni lampadina come una domanda sì/no indipendente.

1.3 Tre famiglie di approcci#

I metodi di classificazione si organizzano in tre famiglie, che differiscono per quanto del problema decidono di modellare:

• Funzione discriminante: si modella direttamente una funzione parametrica che mappa l’input nella classe, e si imparano i parametri dai dati. Nessuna probabilità: il modello produce solo la decisione. Esempi: il perceptron, il K-NN.
• Approccio discriminativo probabilistico: si progetta un modello parametrico della probabilità condizionata $p(C_k \mid \mathbf{x})$, cioè della probabilità che il punto appartenga alla classe $C_k$ dato il valore delle sue feature, e se ne imparano i parametri dai dati. Esempio: la logistic regression.
• Approccio generativo probabilistico: si modellano la likelihood (verosimiglianza) di classe $p(\mathbf{x} \mid C_k)$ e le probabilità a priori delle classi $p(C_k)$, si adattano questi modelli ai dati, e si ricava la probabilità a posteriori con la regola di Bayes:

$$p(C_k \mid \mathbf{x}) = \frac{p(\mathbf{x} \mid C_k)\, p(C_k)}{p(\mathbf{x})}$$

Le tre famiglie sono ordinate per ambizione crescente. Da un modello probabilistico si può sempre ricavare una funzione discriminante: basta predire la classe con la probabilità più alta (la moda della distribuzione). Il viceversa non vale: una funzione discriminante non dice nulla su quanto la decisione sia affidabile. L’approccio generativo, il più ambizioso, modella di fatto la distribuzione congiunta $p(\mathbf{x}, C_k) = p(\mathbf{x} \mid C_k)\, p(C_k)$: conoscendola, si possono non solo classificare punti ma anche generare dati sintetici campionando dalla distribuzione appresa.

In parole semplici: le tre famiglie rispondono a domande sempre più ricche. La funzione discriminante risponde solo “che classe è?”; l’approccio discriminativo risponde “che classe è, e con quale probabilità?”; l’approccio generativo risponde anche “come sono fatti i dati di ciascuna classe?”, al punto da poterne inventare di nuovi. Più si modella, più informazione si ottiene, ma più assunzioni servono e più dati bisogna avere.

In questo capitolo si incontrano rappresentanti di tutte e tre le famiglie: il perceptron (discriminante), la logistic regression (discriminativa probabilistica), Naive Bayes (generativa) e il K-NN (discriminante, ma non parametrica).

2. Modelli lineari generalizzati e geometria della decisione#

2.1 Modelli lineari generalizzati#

In regressione il modello era direttamente la parte lineare $\mathbf{x}^T \mathbf{w} + w_0$: un numero reale, non limitato, e andava benissimo così. In classificazione l’output deve essere un’etichetta discreta oppure una probabilità, quindi un numero reale illimitato non è interpretabile: serve un modo per costringere l’uscita in un insieme o in un intervallo sensato.

Rispetto ai modelli lineari puri della regressione ci sono due osservazioni importanti:

• a causa dell’activation function, $y(\mathbf{x})$ non è più lineare in $\mathbf{w}$: questo complica l’analisi e l’ottimizzazione (in generale si perdono le soluzioni in forma chiusa);
• ciò che resta lineare è la geometria della decisione: il modello divide lo spazio degli input in decision region (regione di decisione), e i confini tra le regioni, detti decision surface (decision surfaces o decision boundaries), corrispondono ai punti in cui $\mathbf{x}^T \mathbf{w} + w_0 = \text{cost}$, che sono iperpiani. È in questo senso che i modelli si dicono ancora “lineari”.

In parole semplici: il modello calcola un punteggio lineare e poi lo passa dentro una funzione che lo “traduce” in etichetta o probabilità. La traduzione è non lineare, ma la linea di confine tra “dico classe 1” e “dico classe 2” resta una retta (un piano, un iperpiano): cambiare l’activation function cambia il significato dell’output, non la forma del confine.

2.2 La funzione discriminante lineare per due classi#

Il modello più semplice della famiglia è la funzione discriminante lineare per un problema binario. Si definisce il punteggio

$$y(\mathbf{x}) = \mathbf{x}^T \mathbf{w} + w_0$$

e si decide con la regola: assegna $\mathbf{x}$ alla classe $C_1$ se $y(\mathbf{x}) \geq 0$, altrimenti alla classe $C_2$. La decision surface è l’insieme dei punti con $y(\mathbf{x}) = 0$: con due variabili di input è una retta nel piano, con tre un piano, in generale un iperpiano in $D$ dimensioni. Si noti un dettaglio di notazione: qui il termine di bias $w_0$ viene tenuto esplicito, invece di assorbirlo nel vettore dei pesi con il trucco della componente costante come in regressione; il motivo è che le proprietà geometriche che seguono si enunciano in modo pulito proprio separando $\mathbf{w}$ da $w_0$. Si noti anche che con due input i parametri sono tre ($w_1$, $w_2$ e $w_0$): servono tutti e tre per poter descrivere una retta qualsiasi del piano, non solo quelle passanti per l’origine.

L’iperpiano non è solo un confine: è un confine orientato. Il vettore $\mathbf{w}$ punta verso il lato positivo, quello dei punti classificati $C_1$; invertendo il segno di $\mathbf{w}$ e $w_0$ il confine resta identico ma l’orientazione si ribalta.

2.3 Geometria dell’iperpiano: ortogonalità e distanze#

Idea chiave: il vettore dei pesi $\mathbf{w}$ è la “bussola” del classificatore: è ortogonale alla decision surface, e il punteggio $y(\mathbf{x})$ misura (a meno di un fattore di scala) la distanza con segno di ogni punto dalla superficie. Il punteggio non dice solo da che parte sta il punto, dice anche quanto la decisione è netta.

Le tre proprietà geometriche fondamentali, con le rispettive giustificazioni:

• La decision surface è ortogonale a $\mathbf{w}$. Si prendano due punti qualsiasi $\mathbf{x}_A$ e $\mathbf{x}_B$ sulla superficie: per definizione $\mathbf{w}^T \mathbf{x}_A + w_0 = 0$ e $\mathbf{w}^T \mathbf{x}_B + w_0 = 0$. Sottraendo le due equazioni, $\mathbf{w}^T (\mathbf{x}_A - \mathbf{x}_B) = 0$: il vettore $\mathbf{x}_A - \mathbf{x}_B$, che è una direzione arbitraria giacente sulla superficie, è ortogonale a $\mathbf{w}$. Poiché questo vale per ogni coppia di punti della superficie, $\mathbf{w}$ è ortogonale alla superficie intera.
• La distanza della superficie dall’origine è $-\dfrac{w_0}{\lVert \mathbf{w} \rVert_2}$. Si prenda un punto $\mathbf{x}$ sulla superficie e lo si proietti sulla direzione ortogonale, cioè su $\mathbf{w}$: la proiezione vale $\dfrac{\mathbf{w}^T \mathbf{x}}{\lVert \mathbf{w} \rVert_2}$, e poiché sulla superficie $\mathbf{w}^T \mathbf{x} = -w_0$, la distanza risulta $-w_0 / \lVert \mathbf{w} \rVert_2$. Il bias controlla quindi la posizione dell’iperpiano, mentre $\mathbf{w}$ ne controlla l’orientazione.
• La distanza con segno di un punto qualsiasi $\mathbf{x}$ dalla superficie è $\dfrac{y(\mathbf{x})}{\lVert \mathbf{w} \rVert_2}$. Se $y(\mathbf{x}) > 0$ il punto sta dal lato positivo e la quantità è la sua distanza vera; se $y(\mathbf{x}) < 0$ il punto sta dal lato negativo e la quantità è la distanza cambiata di segno.

L’ultima proprietà è la più preziosa: il punteggio $y(\mathbf{x})$ funziona da misura di confidenza della classificazione. Più un punto è lontano dalla superficie, più grande è $|y(\mathbf{x})|$ e più il modello è “sicuro” della decisione; un punto vicino alla superficie ha punteggio quasi nullo e la sua classificazione è fragile. Questa idea verrà sfruttata subito per gestire il multiclasse, e tornerà da protagonista molto più avanti nel corso con le Support Vector Machine.

In parole semplici: si immagini l’iperpiano come una staccionata e $\mathbf{w}$ come una freccia piantata perpendicolarmente su di essa. Il punteggio di un punto dice da che lato della staccionata sta (segno) e quanto ne è lontano (valore assoluto). Un punteggio grande e positivo significa “classe positiva, senza dubbi”; un punteggio piccolo significa “sono sul filo”.

2.4 Più di due classi: one-versus-the-rest, one-versus-one, K discriminanti#

Come estendere un classificatore binario a $K$ classi? Le prime due strategie decompongono il problema in tanti sottoproblemi binari:

• One-versus-the-rest: si addestrano $K-1$ classificatori binari, ognuno dei quali distingue una classe $C_i$ da “tutto il resto” (il $K$-esimo è ridondante: se un punto non è di nessuna delle prime $K-1$ classi, è dell’ultima). Il difetto è l’ambiguità: esistono regioni dello spazio in cui più classificatori rivendicano il punto contemporaneamente (per esempio “è di classe 1” e “è di classe 2” insieme), e regioni in cui nessuno lo rivendica.
• One-versus-one: si addestra un classificatore per ogni coppia di classi, $K(K-1)/2$ in totale, ognuno usando solo i punti delle sue due classi. Anche qui restano regioni ambigue, dove i verdetti dei classificatori sono in disaccordo circolare (il primo dice classe 1, il secondo classe 2, il terzo classe 3).

La soluzione pulita sfrutta la nozione di confidenza appena introdotta: invece di combinare verdetti binari secchi, si confrontano i punteggi.

Idea chiave: si usa una funzione discriminante lineare per ogni classe e si assegna il punto alla classe con il punteggio più alto. Confrontare punteggi continui, invece di verdetti sì/no, elimina ogni ambiguità: c’è (quasi) sempre un vincitore unico.

Formalmente, si definiscono $K$ funzioni discriminanti lineari

$$y_k(\mathbf{x}) = \mathbf{x}^T \mathbf{w}_k + w_{k0}, \qquad k = 1, \dots, K$$

e si assegna $\mathbf{x}$ alla classe $C_k$ se $y_k(\mathbf{x}) > y_j(\mathbf{x})$ per ogni $j \neq k$. Servono davvero $K$ modelli (qui la ridondanza non si può sfruttare, perché servono $K$ punteggi da confrontare). Due osservazioni:

• può succedere che tutti i punteggi siano negativi, cioè che ogni modello ritenga il punto “non della propria classe”: si sceglie comunque il punteggio massimo, cioè il modello meno convinto del rifiuto, che è la classificazione più plausibile disponibile;
• il pareggio esatto tra due punteggi continui è un evento di probabilità nulla dal punto di vista teorico; nella pratica a precisione finita si adotta una regola di spareggio convenzionale (per esempio la classe di indice minimo).

Questa costruzione ha anche una proprietà strutturale elegante: le decision region risultanti sono connesse e convesse. La dimostrazione è un argomento di linearità: siano $\mathbf{x}_A, \mathbf{x}_B$ due punti entrambi nella regione $\mathcal{R}_k$, cioè con $y_k(\mathbf{x}_A) > y_j(\mathbf{x}_A)$ e $y_k(\mathbf{x}_B) > y_j(\mathbf{x}_B)$ per ogni $j \neq k$. Ogni punto del segmento che li unisce si scrive come $\alpha \mathbf{x}_A + (1-\alpha)\mathbf{x}_B$ con $0 < \alpha < 1$, e per linearità delle $y_k$:

$$y_k\big( \alpha \mathbf{x}_A + (1-\alpha)\mathbf{x}_B \big) = \alpha\, y_k(\mathbf{x}_A) + (1-\alpha)\, y_k(\mathbf{x}_B) > \alpha\, y_j(\mathbf{x}_A) + (1-\alpha)\, y_j(\mathbf{x}_B) = y_j\big( \alpha \mathbf{x}_A + (1-\alpha)\mathbf{x}_B \big)$$

quindi l’intero segmento appartiene a $\mathcal{R}_k$: la regione è convessa (e in particolare connessa).

In parole semplici: con i verdetti sì/no due giudici possono contraddirsi e lasciare zone di nessuno; con i punteggi c’è sempre una classifica e vince il primo. In più, le regioni che ne risultano sono “senza buchi né rientranze”: se due punti sono della stessa classe, tutta la linea che li congiunge lo è.

2.5 Funzioni base: confini non lineari con macchinari lineari#

Tutto quanto visto finora lavora nello spazio degli input $\mathbf{x}$. Come in regressione, però, la linearità richiesta è nei parametri, non nei dati: si può sostituire $\mathbf{x}$ con un vettore di feature $\boldsymbol{\phi}(\mathbf{x})$ ottenuto applicando funzioni base non lineari, e tutta la matematica resta identica. La conseguenza geometrica è notevole: una decision surface lineare nel feature space corrisponde a una superficie non lineare nello spazio originale. Questo permette di applicare i modelli lineari di classificazione anche a problemi in cui i campioni non sono linearmente separabili.

Esempio concreto: si consideri un problema binario nel piano in cui i punti di una classe stanno al centro e quelli dell’altra li circondano; nessuna retta può separarli. Si definiscano due funzioni base gaussiane $\phi_1, \phi_2$, con centri in due zone diverse del piano: ogni punto viene mappato nella coppia di valori $(\phi_1(\mathbf{x}), \phi_2(\mathbf{x}))$, che misurano quanto il punto è vicino a ciascun centro. Nel feature space così costruito le due classi si dispongono in gruppi separabili con una retta, e quella retta, riportata nello spazio originale, è un confine curvilineo (circolare) che racchiude la classe centrale.

In parole semplici: se i dati non si lasciano tagliare da una retta, non si cambia il coltello, si cambia il tagliere: si trasformano le coordinate dei punti in modo che, nelle nuove coordinate, una retta basti. Il costo è dover scegliere bene le trasformazioni, esattamente come per le basi in regressione.

3. Primo approccio diretto: least squares per la classificazione#

3.1 La costruzione#

La prima idea per imparare i pesi è riciclare quello che già si sa fare: se le classi sono codificate con numeri (0/1 oppure one-hot), perché non trattare la classificazione come una regressione e usare i least squares? La risposta è che si può fare, ma non si deve: la costruzione è tecnicamente lecita e istruttiva, e vederla fallire spiega molto su cosa serve davvero a un classificatore.

Si consideri un problema a $K$ classi con codifica 1-of-K. Ogni classe viene modellata con una funzione lineare $y_k(\mathbf{x}) = \mathbf{w}_k^T \mathbf{x} + w_{k0}$, e in notazione matriciale il modello complessivo è

$$\mathbf{y}(\mathbf{x}) = \widetilde{\mathbf{W}}^T \tilde{\mathbf{x}}$$

dove $\tilde{\mathbf{x}} = (1, \mathbf{x}^T)^T$, e $\widetilde{\mathbf{W}}$ è una matrice $(D+1) \times K$ la cui $k$-esima colonna è $\tilde{\mathbf{w}}_k = (w_{k0}, \mathbf{w}_k^T)^T$. Raccogliendo gli input nella matrice $\widetilde{\mathbf{X}}$ ($N \times (D+1)$, una riga per campione) e i target one-hot nella matrice $\mathbf{T}$ ($N \times K$, una riga per campione), il problema è esattamente una regressione lineare a output multipli, e la soluzione ai least squares è quella nota:

$$\widetilde{\mathbf{W}} = \big( \widetilde{\mathbf{X}}^T \widetilde{\mathbf{X}} \big)^{-1} \widetilde{\mathbf{X}}^T \mathbf{T}$$

Un nuovo campione $\tilde{\mathbf{x}}_{new}$ viene poi assegnato alla classe $C_k$ se la $k$-esima componente dell’output, $t_k = \tilde{\mathbf{x}}_{new}^T \tilde{\mathbf{w}}_k$, è la più grande di tutte.

3.2 Perché non funziona#

Idea chiave: i least squares assumono implicitamente “modello lineare più rumore gaussiano attorno al target”. In classificazione questa assunzione è falsa: i punti di una classe non si addensano attorno al valore 1, si spargono per tutta la loro regione. Il risultato è che il metodo punisce anche i punti classificati “troppo bene”, e un singolo punto lontano trascina via il confine.

Per capire il fallimento conviene un esempio a una dimensione, con punti di classe “rossa” (target 1) a sinistra e punti delle altre classi (target 0) a destra, illustrato nella figura qui sotto e da leggere così:

• Pannello di sinistra (senza outlier): la regressione ai least squares trova la retta che passa vicino ai valori 1 sui punti rossi e ai valori 0 sugli altri, e il decision boundary (confine di decisione) cade dove la retta attraversa la soglia $0.5$, in mezzo ai due gruppi. Fin qui tutto funziona.
• L’outlier: si aggiunga ora un punto rosso molto più a sinistra, lontanissimo dal confine. Dal punto di vista della classificazione è un punto facilissimo, chiaramente rosso, che non dovrebbe spostare nulla.
• La retta tratteggiata (pannello di destra): è la vecchia retta, la stessa del pannello di sinistra, prolungata fino all’outlier. Laggiù produce un valore molto maggiore di 1, mentre il target dell’outlier è 1: tra il punto e la retta si apre quindi un residuo enorme (il tratteggio rosso verticale) che, elevato al quadrato, domina la loss.
• La retta continua: è la retta rifittata su tutti i punti, outlier compreso. Per contenere quel residuo si è appiattita, e il punto in cui attraversa $0.5$, cioè il nuovo confine, si è spostato in modo significativo verso l’outlier stesso (in figura, dal vecchio confine “prima” alla verticale più a sinistra).
• Il paradosso: aggiungere un punto ovviamente rosso restringe la regione classificata come rossa, fino a sbagliare punti rossi vicini al confine che prima erano corretti, come il punto marcato “sbagliato” in figura.

I problemi strutturali sono quindi due:

• Sensibilità estrema agli outlier “corretti”: punti lontani dal confine ma dal lato giusto vengono penalizzati dalla loss quadratica come se fossero errori, perché il loro punteggio è “troppo” positivo. Un classificatore sensato dovrebbe premiare, non punire, le classificazioni molto sicure; il least squares fa l’opposto, perché eredita dalla regressione l’idea che i target debbano essere centrati esattamente su 1 e 0.
• Distribuzione dell’output priva di senso probabilistico: gli output del modello non sono vincolati in $[0, 1]$ e non si possono leggere come probabilità; nei problemi multiclasse, inoltre, le decision region possono risultare pesantemente distorte anche senza outlier, fino al caso patologico in cui una classe non risulta mai vincente su nessuna regione dello spazio (fenomeno noto in letteratura come masking).

In parole semplici: il least squares gioca a un gioco sbagliato: cerca di far passare una retta vicino a dei numeri (1 e 0), mentre il gioco vero è mettere un confine tra due gruppi. Un punto lontano ma ovviamente ben classificato è irrilevante per il confine, ma per la retta è un errore gigantesco da rincorrere. Serve una loss pensata per i confini, non per i numeri: è esattamente quello che fanno il perceptron e la logistic regression.

4. Il perceptron#

4.1 Modello e criterio del perceptron#

Il perceptron è un modello discriminante lineare proposto da Rosenblatt nel 1958 insieme a un algoritmo di apprendimento sequenziale: non è tecnologia recente, ma è il progenitore diretto delle reti neurali e il primo esempio di algoritmo che impara dai propri errori punto per punto. È progettato per problemi binari, con codifica delle classi $t \in \{-1, +1\}$ (la scelta che rende la matematica più compatta). Il modello è un modello lineare generalizzato con la funzione segno come attivazione:

$$y(\mathbf{x}) = \operatorname{sign}\big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}) \big), \qquad \operatorname{sign}(a) = \begin{cases} +1 & a \geq 0 \\ -1 & a < 0 \end{cases}$$

dove $\boldsymbol{\phi}$ è un generico vettore di feature con $\phi_0(\mathbf{x}) = 1$ a fare da bias (lavorare nel feature space non costa nulla e dà generalità). L’obiettivo è trovare $\mathbf{w}$ tale che $\mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) \geq 0$ per i punti di classe positiva e $\mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) < 0$ per gli altri; grazie alla codifica $\pm 1$, le due condizioni si compattano in una sola: $\mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n)\, t_n > 0$ per ogni $n$.

Che loss minimizzare? La scelta più naturale sarebbe il numero di punti misclassificati, ma è una pessima funzione da ottimizzare: è costante a tratti, il suo gradiente è nullo quasi ovunque, e non offre alcuna indicazione sulla direzione in cui muovere i pesi. La scelta giusta è misurare non quanti errori si fanno, ma quanto grandi sono: e la grandezza di un errore è la distanza del punto misclassificato dal confine, cioè (a meno della scala di $\mathbf{w}$) il suo punteggio.

Il gioco dei segni funziona così: se un punto negativo ($t_n = -1$) viene classificato positivo, il suo punteggio $\mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_n)$ è positivo, quindi il prodotto punteggio per target è negativo, e più il modello era “convinto” (punteggio grande) più il prodotto è negativo, cioè più l’errore è grave; simmetricamente per un punto positivo classificato negativo. Il segno meno davanti alla somma rende ogni contributo positivo, così la loss totale è la quantità complessiva di errore da abbattere.

In parole semplici: il perceptron non conta gli errori, li pesa: sbagliare su un punto vicinissimo al confine è veniale, sbagliare con grande sicurezza su un punto lontano è grave. Questa scelta rende la loss “liscia a tratti” e ottimizzabile con il gradiente, cosa impossibile con il semplice conteggio degli errori.

4.2 L’algoritmo di apprendimento#

La minimizzazione di $L_P$ si fa con il gradient descent (discesa del gradiente) stocastica: la loss è una somma di termini, uno per punto misclassificato, e a ogni passo si corregge il contributo di un solo punto. Il gradiente del singolo termine rispetto a $\mathbf{w}$ è semplicemente $-\boldsymbol{\phi}(\mathbf{x}_n) t_n$, quindi l’aggiornamento è

$$\mathbf{w}^{(k+1)} = \mathbf{w}^{(k)} + \alpha\, \boldsymbol{\phi}(\mathbf{x}_n)\, t_n$$

C’è una particolarità sul learning rate $\alpha$. Il perceptron dipende da $\mathbf{w}$ solo attraverso il segno del punteggio: moltiplicando $\mathbf{w}$ per una costante positiva la funzione di classificazione non cambia affatto (le soluzioni sono definite a meno di scala, e per lo stesso motivo, se esiste una soluzione, ne esistono infinite equivalenti). Di conseguenza il valore di $\alpha$ non incide sulla qualità della soluzione ma solo sulla scala dei pesi, e per convenzione si pone $\alpha = 1$. L’algoritmo completo:

1. Inizializzare $\mathbf{w}_0$; porre $k \leftarrow 0$.
2. Ripetere: $k \leftarrow k + 1$; selezionare il campione $n = k \bmod N$.
3. Calcolare la predizione $\hat{t}_n = \operatorname{sign}\big(\mathbf{w}_k^T \boldsymbol{\phi}(\mathbf{x}_n)\big)$; se $\hat{t}_n \neq t_n$, aggiornare $\mathbf{w}_{k+1} \leftarrow \mathbf{w}_k + \boldsymbol{\phi}(\mathbf{x}_n)\, t_n$.
4. Fermarsi quando nessun punto del dataset risulta misclassificato.

Lo stesso algoritmo in pseudocodice C-like, per fissare i dettagli implementativi:

// w: vettore dei pesi (dim d), inizializzato a piacere
// X: N campioni phi(x_n), ciascuno di dimensione d; T: le rispettive etichette +-1
void perceptron_train(double *w, double **X, int *T, int N, int d) {
    int all_correct;

    do {
        all_correct = 1;               // ipotesi: questa epoca non trova errori
        for (int n = 0; n < N; n++) {
            double score = dot(w, X[n], d);       // w^T phi(x_n)
            int t_hat = (score >= 0) ? 1 : -1;    // sign(...)

            if (t_hat != T[n]) {                  // punto misclassificato
                for (int j = 0; j < d; j++)
                    w[j] += X[n][j] * T[n];       // w <- w + phi(x_n) t_n
                all_correct = 0;                  // errore trovato: serve un'altra epoca
            }
        }
    } while (!all_correct);
    // esce solo quando un'intera epoca non trova nessun errore;
    // se i dati non sono linearmente separabili, questo non accade mai
}

Geometricamente ogni aggiornamento è una rotazione del confine: $\mathbf{w}$ è ortogonale alla decision surface, e sommargli il vettore $\boldsymbol{\phi}(\mathbf{x}_n) t_n$ lo inclina verso la direzione che classifica correttamente il punto appena sbagliato; il confine, che segue $\mathbf{w}$, ruota di conseguenza.

Una conseguenza pratica importante: la soluzione finale dipende dall’ordine di presentazione dei dati (oltre che dall’inizializzazione). Per questo, a differenza della regressione lineare in forma chiusa dove l’ordine è irrilevante, con il perceptron è buona pratica rimescolare i dati (shuffling) prima dell’addestramento, per non ereditare distorsioni dall’ordine di raccolta.

In parole semplici: l’algoritmo scorre i punti uno alla volta; se il punto è classificato bene non tocca nulla, se è sbagliato “tira” il confine verso la correzione di quel punto. Girando e rigirando sul dataset, se una separazione esiste, prima o poi tutti i punti risultano dal lato giusto e l’algoritmo si ferma.

4.3 Convergenza e limiti#

Ogni singolo aggiornamento riduce l’errore sul punto usato per l’aggiornamento: sostituendo la regola di update nel contributo di quel punto,

$$-\mathbf{w}^{(k+1)T} \boldsymbol{\phi}(\mathbf{x}_n)\, t_n = -\mathbf{w}^{(k)T} \boldsymbol{\phi}(\mathbf{x}_n)\, t_n - \big\lVert \boldsymbol{\phi}(\mathbf{x}_n)\, t_n \big\rVert^2 < -\mathbf{w}^{(k)T} \boldsymbol{\phi}(\mathbf{x}_n)\, t_n$$

perché la norma al quadrato sottratta è strettamente positiva. Attenzione però: questo non implica che la loss complessiva diminuisca a ogni passo. La rotazione del confine che sistema un punto può far finire dal lato sbagliato altri punti che prima erano corretti: la loss totale può oscillare, e la sua discesa non è monotona.

Il teorema è forte ma lascia aperte due domande, che sono i veri limiti pratici dell’algoritmo:

• Quanti passi? Il numero di passi necessari può essere molto grande e non è noto in anticipo: in pratica è difficile distinguere un problema non separabile (per cui l’algoritmo non convergerà mai) da uno separabile ma a convergenza lenta.
• Quale soluzione? Se il dataset è separabile le soluzioni sono in generale infinite, e quella trovata dipende dall’inizializzazione dei pesi e dall’ordine di presentazione dei dati: l’algoritmo non esprime alcuna preferenza tra i tanti confini validi.

A questi si aggiungono i limiti strutturali: il perceptron è solo binario (e l’estensione multiclasse con il trucco dei punteggi non funziona bene), e soprattutto, se i dati non sono separabili, l’algoritmo non converge e non gode nemmeno di una proprietà “anytime”: poiché la loss non decresce monotonicamente, fermarsi dopo mille iterazioni non garantisce una soluzione migliore che fermarsi dopo cinquecento. Nei problemi reali, dove la separabilità perfetta è l’eccezione, tutto questo rende il perceptron difficile da usare: serve un approccio che gestisca l’incertezza in modo nativo, ed è la logistic regression.

In parole semplici: su un problema “pulito” (classi separabili) il perceptron arriva sicuramente a una soluzione perfetta, anche se non si sa quando né quale. Su un problema “sporco” gira all’infinito senza una nozione di soluzione buona, e non c’è neanche la consolazione che più lo si lascia girare meglio è. È un ottimo primo algoritmo, ma non un algoritmo da mondo reale.

5. L’approccio discriminativo probabilistico: logistic regression#

5.1 Il modello: una sigmoide su un punteggio lineare#

La logistic regression è la tecnica più popolare della famiglia discriminativa probabilistica: si modella direttamente la probabilità condizionata della classe dato l’input, senza pretendere di descrivere come sono distribuiti gli input stessi. Attenzione al nome, fonte inesauribile di confusione: si chiama regression per ragioni storiche, ma è una tecnica di classificazione.

Serve una funzione parametrica il cui output sia una probabilità valida, cioè un numero in $[0, 1]$. La scelta della logistic regression è la funzione sigmoide (o logistica) applicata al solito punteggio lineare:

La sigmoide è una “S” morbida: vale $0$ a $-\infty$, $1/2$ in $0$, $1$ a $+\infty$. Detto $z = \mathbf{w}^T \boldsymbol{\phi}$ il punteggio, la lettura è naturale: punteggio molto positivo, probabilità di classe positiva vicina a 1; punteggio molto negativo, probabilità vicina a 0; punteggio nullo, massima incertezza (probabilità $1/2$). Essendo il problema binario, basta modellare la probabilità della classe positiva: quella della negativa è il complemento a 1.

Nonostante la non linearità della sigmoide, la decision surface resta lineare: si predice $C_1$ quando $p(C_1 \mid \boldsymbol{\phi}) > 1/2$, e per la monotonia della sigmoide questo accade esattamente quando $\mathbf{w}^T \boldsymbol{\phi} > 0$. Il confine è quindi ancora l’iperpiano $\mathbf{w}^T \boldsymbol{\phi} = 0$: nel piano una retta, in tre dimensioni un piano, in generale un iperpiano nel feature space. In generale, per qualunque modello lineare generalizzato, la decision surface si ottiene ponendo a zero l’argomento dell’activation function.

In parole semplici: la logistic regression calcola lo stesso punteggio lineare del perceptron, ma invece di trasformarlo in un secco “sì/no” lo spalma dolcemente tra 0 e 1 e lo consegna come probabilità. Il decision boundary è nello stesso posto; quello che cambia è tutto ciò che sta intorno: ora il modello sa dire “80% classe positiva” invece di limitarsi a “classe positiva”.

5.2 Maximum likelihood e cross-entropy#

Idea chiave: i pesi si imparano con la maximum likelihood, come nella lettura probabilistica della regressione lineare: si cerca il $\mathbf{w}$ che rende massima la probabilità, calcolata dal modello, di osservare esattamente le etichette del dataset. Il logaritmo negativo di questa probabilità è la loss function (funzione di perdita), e ha un nome importante: cross-entropy.

La probabilità di osservare il target $t_n \in \{0,1\}$ del singolo campione si modella con una distribuzione di Bernoulli il cui parametro è l’output del modello, $y_n = \sigma\big(\mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n)\big)$:

$$p(t_n \mid \mathbf{x}_n, \mathbf{w}) = y_n^{t_n} \, (1 - y_n)^{1 - t_n}$$

La scrittura con gli esponenti è solo un modo compatto di dire due cose insieme: se $t_n = 1$ il secondo fattore ha esponente zero e resta $y_n$ (la probabilità che il modello dà alla classe positiva); se $t_n = 0$ resta $1 - y_n$ (la probabilità della classe negativa). In entrambi i casi il fattore è “la probabilità che il modello assegna alla classe giusta per quel punto”. Assumendo i campioni indipendenti e identicamente distribuiti, la likelihood dell’intero dataset è il prodotto:

$$p(\mathbf{t} \mid \mathbf{X}, \mathbf{w}) = \prod_{n=1}^{N} y_n^{t_n} \, (1 - y_n)^{1 - t_n}$$

Massimizzare un prodotto è scomodo; come sempre si passa al logaritmo (monotono, non sposta il massimo, trasforma prodotti in somme e fa scendere gli esponenti) e si cambia segno per avere una loss da minimizzare.

In parole semplici: per ogni punto del dataset si chiede al modello “quanta probabilità dai alla classe vera di questo punto?” e si prende il logaritmo (che punisce durissimamente le probabilità vicine a zero, cioè gli errori fatti con sicurezza). La cross-entropy è la somma di queste penalità: minimizzarla significa costringere il modello a dare probabilità alte alle risposte giuste.

5.3 Il gradiente e l’ottimizzazione#

In regressione lineare il logaritmo della likelihood gaussiana era una funzione quadratica dei pesi, e annullare il gradiente dava una soluzione in forma chiusa. Qui non succede: $y_n$ contiene la sigmoide, il logaritmo della sigmoide non è quadratico in $\mathbf{w}$, e non esiste soluzione in forma chiusa. Il gradiente però si calcola benissimo, e la struttura a somma di termini indipendenti (uno per punto) permette il gradient descent anche in versione stocastica/online.

Il calcolo usa la regola della catena sul singolo termine $L_n$. Primo fattore, la derivata della loss rispetto all’output del modello (regola di derivazione del logaritmo):

$$\frac{\partial L_n}{\partial y_n} = -\frac{t_n}{y_n} + \frac{1 - t_n}{1 - y_n} = \frac{y_n - t_n}{y_n (1 - y_n)}$$

Secondo fattore, il gradiente dell’output rispetto ai pesi. Qui interviene una proprietà notevole della sigmoide, che vale la pena ricordare a sé:

$$\sigma'(a) = \sigma(a)\,\big(1 - \sigma(a)\big) \qquad \Longrightarrow \qquad \nabla_{\mathbf{w}}\, y_n = y_n (1 - y_n)\, \boldsymbol{\phi}(\mathbf{x}_n)$$

(la derivata dell’argomento $\mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_n)$ rispetto a $\mathbf{w}$ è $\boldsymbol{\phi}(\mathbf{x}_n)$). Moltiplicando i due fattori, il denominatore $y_n(1-y_n)$ si semplifica esattamente e resta un’espressione pulitissima:

$$\nabla L(\mathbf{w}) = \sum_{n=1}^{N} \big( y_n - t_n \big)\, \boldsymbol{\phi}(\mathbf{x}_n)$$

Il gradiente ha la stessa forma “errore per feature” già vista nell’algoritmo LMS della regressione: il contributo di ogni punto è la differenza tra la probabilità predetta e il target, moltiplicata per il vettore di feature. La regola di aggiornamento stocastica è quindi

$$\mathbf{w} \leftarrow \mathbf{w} - \alpha \big( y_n - t_n \big)\, \boldsymbol{\phi}(\mathbf{x}_n)$$

In parole semplici: niente formula magica in un colpo solo, ma una ricetta iterativa semplicissima: per ogni punto si guarda di quanto la probabilità predetta manca il bersaglio (un numero tra $-1$ e $1$) e si correggono i pesi in proporzione, lungo le feature attive. Se il modello dà 0.9 a un punto che è davvero positivo, la correzione è piccola; se dà 0.1, la correzione è grande.

5.4 Proprietà: convessità, convergenza, test statistici#

La loss di cross-entropy della logistic regression è una funzione convessa dei pesi: salvo casi patologici ammette un unico minimo, e l’ottimizzazione a gradiente lo raggiunge indipendentemente dall’inizializzazione e dall’ordine dei dati. Il confronto con il perceptron è istruttivo e va saputo all’esame:

• Perceptron: se i dati sono separabili converge a una soluzione esatta in un numero finito di passi, ma la soluzione trovata dipende da inizializzazione e ordine dei dati; se non sono separabili, non converge affatto.
• Logistic regression: converge sempre, verso la stessa soluzione qualunque siano inizializzazione e ordine (la loss è convessa), ma la convergenza è solo asintotica: si segue il gradiente avvicinandosi al minimo senza mai raggiungerlo esattamente in un numero finito di passi.

Un’ultima proprietà collega la logistic regression all’apparato statistico della regressione lineare. La funzione inversa della sigmoide si chiama logit:

$$\operatorname{logit}(y) = \ln \frac{y}{1 - y} = \mathbf{w}^T \boldsymbol{\phi}$$

applicando il logit all’output si recupera il modello lineare sottostante, e su di esso si possono eseguire i test statistici sui coefficienti (test t, p-value) visti nel capitolo sulla regressione, per chiedersi quali feature siano statisticamente significative. In pratica il modello si addestra con librerie standard (in scikit-learn la classe LogisticRegression).

5.5 Il caso multiclasse: softmax#

Per estendere la logistic regression a $K$ classi non basta più una sola probabilità: serve una distribuzione di probabilità completa sulle classi, cioè $K$ numeri non negativi che sommano a 1. L’idea è avere un punteggio lineare per classe, con un vettore di pesi separato $\mathbf{w}_k$ per ciascuna (con tre classi, tre vettori di pesi e tre equazioni), e normalizzare i punteggi con la trasformazione softmax:

La costruzione garantisce una distribuzione valida: gli esponenziali rendono tutto positivo, e poiché tutte le probabilità condividono lo stesso denominatore, che è esattamente la somma dei numeratori, la somma su $k$ vale 1. La softmax è la generalizzazione naturale della sigmoide: esalta il punteggio massimo (da cui il nome, un “massimo morbido”) ma conserva l’informazione su quanto le altre classi fossero vicine.

L’addestramento ricalca il caso binario. Con la codifica 1-of-K dei target ($t_{nk} = 1$ se il campione $n$ è di classe $k$, zero altrimenti), la likelihood è

$$p(\mathbf{T} \mid \mathbf{X}, \mathbf{w}_1, \dots, \mathbf{w}_K) = \prod_{n=1}^{N} \prod_{k=1}^{K} y_{nk}^{\,t_{nk}}$$

dove $y_{nk} = p(C_k \mid \boldsymbol{\phi}(\mathbf{x}_n))$: per ogni punto, tutti i fattori con $t_{nk} = 0$ valgono 1 e sopravvive solo la probabilità che il modello assegna alla classe vera del punto. La loss è la cross-entropy multiclasse

$$L(\mathbf{w}_1, \dots, \mathbf{w}_K) = -\sum_{n=1}^{N} \sum_{k=1}^{K} t_{nk} \ln y_{nk}$$

e il gradiente rispetto al vettore di pesi della classe $j$ ha la stessa forma familiare “errore per feature”:

$$\nabla_{\mathbf{w}_j} L = \sum_{n=1}^{N} \big( y_{nj} - t_{nj} \big)\, \boldsymbol{\phi}(\mathbf{x}_n)$$

A ogni passo di gradient descent si aggiornano quindi tutti i $K$ vettori di pesi, ciascuno in proporzione al proprio errore di probabilità su quel punto.

In parole semplici: nel multiclasse ogni classe ha la sua “antenna” (il suo vettore di pesi) che produce un punteggio; la softmax converte la classifica dei punteggi in percentuali che sommano a 100. L’addestramento premia l’antenna della classe giusta e smorza le altre, punto dopo punto, con la stessa regola errore per feature del caso binario.

5.6 Il perceptron rivisitato: interpretazione probabilistica#

C’è un legame profondo tra logistic regression e perceptron. Se nel modello probabilistico si sostituisce la sigmoide con una funzione a gradino (step function: 0 a sinistra dello zero, 1 a destra) e si ripercorre la derivazione a maximum likelihood, la regola di aggiornamento che ne risulta è esattamente la regola del perceptron. In altre parole: il perceptron è una logistic regression in cui la probabilità condizionata di classe è modellata da un gradino secco invece che da una transizione morbida.

Questa scoperta è preziosa perché dà al perceptron un’interpretazione probabilistica a posteriori: l’algoritmo era stato progettato come puro approccio diretto, senza probabilità in mente, ma risulta equivalente a un preciso modello probabilistico stimato a maximum likelihood. È lo stesso schema già visto in regressione, dove i ordinary least squares (OLS) erano risultati equivalenti alla maximum likelihood sotto rumore gaussiano: ancora una volta, un metodo “ingegneristico” nasconde dietro di sé assunzioni probabilistiche precise, e renderle esplicite aiuta a capire quando il metodo è appropriato e quando no.

In parole semplici: perceptron e logistic regression sono la stessa macchina con due manopole diverse: il primo decide con un interruttore on/off, la seconda con una manopola graduale. La manopola graduale è quasi sempre preferibile: dà probabilità, ha una loss convessa e converge anche quando i dati non sono separabili.

6. L’approccio generativo: Naive Bayes#

6.1 Modellare la distribuzione congiunta#

Nell’approccio generativo l’obiettivo è imparare la distribuzione congiunta di input e classe, $p(\mathbf{x}, C_k)$. Tipicamente la si fattorizza in due pezzi da apprendere separatamente: la likelihood di classe $p(\mathbf{x} \mid C_k)$ (come sono distribuiti gli input di ciascuna classe) e il prior di classe $p(C_k)$ (quanto è frequente ciascuna classe). Dalla coppia si ricava tutto: la congiunta come prodotto, e la posteriori con la regola di Bayes,

$$p(C_k \mid \mathbf{x}) = \frac{p(\mathbf{x} \mid C_k)\, p(C_k)}{p(\mathbf{x})} \;\propto\; p(\mathbf{x} \mid C_k)\, p(C_k)$$

dove il denominatore $p(\mathbf{x})$ è uguale per tutte le classi e quindi irrilevante ai fini del confronto. Perché prendersi il disturbo di modellare così tanto? Perché la congiunta permette anche di generare nuovi dati sintetici campionando da essa, cosa impossibile per gli approcci discriminativi. Il prezzo è che $p(\mathbf{x} \mid C_k)$ è una distribuzione multivariata su $M$ feature, e stimare una distribuzione multivariata generale richiede moltissimi dati.

6.2 L’assunzione naive#

Idea chiave: per rendere trattabile la stima della likelihood multivariata, Naive Bayes assume che le feature siano condizionatamente indipendenti data la classe: dentro ogni classe, ogni feature si distribuisce per conto suo. L’assunzione è quasi sempre falsa (da cui il nome “naive”, ingenuo), ma trasforma un problema di stima multivariata in $M$ facili problemi univariati, e in pratica funziona sorprendentemente bene.

Senza l’assunzione bisognerebbe apprendere, per ogni classe, una distribuzione congiunta su $M$ variabili, con tutte le loro correlazioni; con l’assunzione bastano $M$ distribuzioni a una variabile per classe, ognuna stimabile con pochissimi parametri. L’assunzione deve valere (o meglio, viene imposta) per ogni classe.

In parole semplici: Naive Bayes finge che, una volta nota la classe, le feature non si parlino tra loro: per descrivere i fiori setosa basta sapere separatamente come si distribuisce la lunghezza del petalo e come la larghezza, ignorando che le due misure sono correlate. È una semplificazione grossolana, ma riduce drasticamente ciò che va imparato dai dati.

6.3 Addestramento e predizione MAP#

L’addestramento stima prior e verosimiglianze per maximum likelihood, e le stime risultano semplicissime:

• Prior di classe: si modella con una distribuzione multinomiale (una distribuzione discreta sulle $K$ classi), e la stima ML è la frequenza relativa di ciascuna classe nel dataset: $p(C_k) = N_k / N$, dove $N_k$ è il numero di campioni di classe $k$.
• Likelihood delle feature continue: la scelta standard è una gaussiana per feature e per classe, i cui parametri si stimano con media campionaria e deviazione standard campionaria dei valori di quella feature ristretti ai campioni di quella classe (in questa versione il metodo si chiama Gaussian Naive Bayes; in scikit-learn la classe è GaussianNB).

La predizione su un nuovo punto $\mathbf{x}$ sceglie la classe con la massima probabilità a posteriori, cioè una decisione MAP (massimo a posteriori):

$$\hat{C} = \arg\max_{k} \; p(C_k) \prod_{j=1}^{M} p(x_j \mid C_k)$$

Si noti che Naive Bayes gestisce il multiclasse in modo nativo: non serve alcuna decomposizione in problemi binari, basta confrontare le posteriori delle $K$ classi. Sul dataset Iris a tre classi, per esempio, il metodo produce direttamente le tre decision region (con confini in generale non lineari, perché il logaritmo del rapporto tra posteriori gaussiane con varianze diverse contiene termini quadratici) e la relativa matrice di confusione $3 \times 3$.

In parole semplici: addestrare Naive Bayes significa fare statistiche elementari sul dataset: contare quanto è frequente ogni classe, e per ogni classe calcolare media e deviazione standard di ogni feature. Predire significa chiedersi, per ogni classe, “quanto è plausibile che un punto così venga da questa classe?” e scegliere la più plausibile, pesando anche quanto la classe è comune.

6.4 Generare dati sintetici e una nota sul nome#

Essendo generativo, Naive Bayes può fare una cosa preclusa agli altri metodi del capitolo: generare campioni artificiali. La ricetta segue la fattorizzazione del modello: si campiona prima una classe dalla multinomiale appresa, poi, per ciascuna feature, un valore dalla gaussiana di quella feature in quella classe. Sul dataset Iris i punti sintetici così generati si dispongono in modo credibile attorno ai punti veri di ciascuna specie; la qualità dei dati generati dipende ovviamente da quanto bene il modello (con la sua assunzione naive) rappresenta i dati reali. Questa capacità si usa per esempio per aumentare artificialmente un dataset (data augmentation).

Attenzione infine a un equivoco terminologico da esame: Naive Bayes non è un metodo bayesiano. Usa il teorema di Bayes per ricavare la posteriori delle classi, ma i suoi parametri (frequenze, medie, deviazioni standard) sono stimati con la maximum likelihood, come numeri puntuali: non c’è alcuna distribuzione di probabilità sui parametri, che è il tratto distintivo dei metodi bayesiani veri (visti per la regressione e ripresi più avanti nel corso).

7. Un metodo non parametrico: K-Nearest Neighbors#

7.1 Dal vicino più vicino ai K vicini#

Tutti i metodi visti finora sono parametrici: apprendere significa trovare i valori di un insieme di parametri fissato in anticipo. Il nearest neighbor ribalta la prospettiva con un’idea disarmante: per classificare un punto nuovo, si guarda al punto del dataset che gli somiglia di più e si copia la sua etichetta. Come criterio di somiglianza serve solo una distanza tra punti, tipicamente quella euclidea.

Non c’è alcun addestramento: nessun parametro da stimare, nessuna ottimizzazione. Il “modello” è il dataset stesso, che va tenuto tutto in memoria e consultato a ogni predizione.

La generalizzazione naturale è il K-Nearest Neighbors (K-NN): invece del solo punto più vicino si considerano i $K$ punti più vicini, e si predice la classe che compare più volte tra di essi (majority voting, cioè la moda delle etichette dei vicini). Il metodo funziona anche per la regressione: in quel caso si predice la media dei target dei $K$ vicini. Esistono molte varianti: pesare il voto di ciascun vicino in base alla distanza, usare distanze più sofisticate di quella euclidea, e così via.

In parole semplici: il K-NN applica il proverbio “dimmi con chi vai e ti dirò chi sei”: un punto nuovo viene classificato guardando i suoi vicini nel dataset e adeguandosi alla maggioranza. Non impara nessuna regola: si limita a ricordare tutti gli esempi e a consultarli al momento del bisogno.

7.2 K come manopola di regolarizzazione#

Le decision surface del K-NN sono tutt’altro che lineari: dipendono interamente dalla posizione dei punti nello spazio. Sul dataset Iris il confronto tra due valori di $K$ è illuminante:

• con $K = 1$ il decision boundary è frastagliato e insegue ogni singolo punto, comprese le anomalie: ogni punto di training “possiede” la propria piccola regione. Modello a bassissimo bias ma altissima varianza: cambiando pochi punti del dataset il confine cambia drasticamente;
• con $K = 20$ il confine diventa molto più liscio e regolare: le anomalie isolate vengono messe in minoranza dal voto dei vicini. Cresce il bias (il confine non può più seguire dettagli fini), cala la varianza.

Il parametro $K$ agisce quindi da regolarizzatore, in perfetta analogia con il coefficiente $\lambda$ della ridge regression: aumentandolo si scambia flessibilità (bias più alto) con stabilità (varianza più bassa). La scelta di $K$ è il tipico compromesso da tarare sul problema.

In parole semplici: $K$ decide quante opinioni ascoltare prima di decidere. Con $K=1$ ci si fida ciecamente del primo passante (e si copia anche il suo errore); con $K$ grande si fa un sondaggio di quartiere, più robusto ma meno sensibile alle sfumature locali. Né troppo pochi né troppi: come sempre, il giusto sta nel mezzo e dipende dai dati.

8. Valutare un classificatore#

8.1 La matrice di confusione#

Come l’$R^2$ riassume la qualità di una regressione, servono indici per la qualità di un classificatore. Per la classificazione binaria lo strumento di partenza è una tabella che incrocia verità e predizioni.

Le celle sulla diagonale (TP e TN) sono i successi; quelle fuori diagonale (FP e FN) sono i due tipi di errore, e l’obiettivo è renderle più piccole possibile. La matrice si estende al multiclasse aggiungendo una riga e una colonna per classe: sulla diagonale i punti classificati correttamente, fuori diagonale ogni tipo di confusione tra coppie di classi.

8.2 Accuracy, precision, recall e F1#

Dalla matrice di confusione si derivano indici sintetici, ciascuno con una domanda precisa a cui risponde:

• Accuracy: $\dfrac{TP + TN}{N}$, la frazione di punti classificati correttamente sul totale. Il complemento $1 - \text{accuracy}$ si chiama errore di classificazione.
• Precision: $\dfrac{TP}{TP + FP}$, la frazione di veri positivi tra tutti i punti predetti positivi. Precision vicina a 1 significa pochi falsi positivi: quando il modello dice “positivo”, ci si può fidare.
• Recall: $\dfrac{TP}{TP + FN}$, la frazione di veri positivi tra tutti i punti realmente positivi. Recall vicina a 1 significa pochi falsi negativi: il modello si lascia sfuggire pochi positivi veri.
• F1 score: la media armonica di precision e recall, $F_1 = \dfrac{2 \cdot P \cdot R}{P + R}$: alta solo se entrambe sono alte, quindi riassume in un numero il controllo complessivo sugli errori.

Un’avvertenza importante: precision, recall e F1 non sono simmetriche rispetto alla scelta di quale classe chiamare “positiva”, che è del tutto arbitraria; scambiando positivi e negativi i valori cambiano, e a volte è informativo calcolare gli indici in entrambe le direzioni.

In parole semplici: l’accuracy dice “quante ne azzecco in totale”, ma può ingannare (con il 99% di punti negativi, un modello che dice sempre “negativo” ha accuracy 0.99 ed è inutile). La precision chiede “quando dico positivo, quanto spesso ho ragione?”, la recall chiede “dei positivi veri, quanti ne trovo?”; l’F1 le combina in modo severo: basta che una delle due crolli e crolla anche lui.

9. Come scegliere l’approccio#

9.1 Parametrico contro non parametrico#

La distinzione più strutturale tra i metodi del capitolo è questa:

• Metodi parametrici (perceptron, logistic regression, Naive Bayes): apprendere significa trovare il valore di un numero finito e prefissato di parametri (i pesi $\mathbf{w}$; per Naive Bayes, frequenze, medie e deviazioni standard). Dopo l’addestramento il dataset non serve più: per predire basta il modello, compatto e veloce da valutare.
• Metodi non parametrici (K-NN): non c’è alcun addestramento e non si apprende alcun parametro; il modello è il dataset. La predizione richiede di conservare tutti i dati in memoria e, nel caso peggiore, di scorrerli tutti a ogni interrogazione.

Le conseguenze pratiche di questa differenza (memoria, costo di addestramento, costo di predizione, possibilità di iniettare conoscenza a priori) guidano la scelta del metodo nei diversi scenari applicativi; il ragionamento dettagliato, in tipico stile esame, è sviluppato nell’esercizio 10.4.

9.2 Confronto sinottico dei metodi#

In parole semplici: non esiste il classificatore migliore in assoluto: esiste quello giusto per i vincoli del problema. Servono probabilità? Logistic regression o Naive Bayes. Serve generare dati? Naive Bayes. Zero tempo di addestramento e tanta memoria disponibile? K-NN. Predizioni velocissime su hardware limitato? Un parametrico. All’esame conta saper motivare la scelta, non recitare un nome.

10. Esercizi d’esame svolti#

10.1 Codificare una variabile qualitativa#

Traccia. Quale tra le seguenti è un esempio di variabile qualitativa: altezza, età, velocità, colore? Fornire poi un metodo per convertire la variabile qualitativa in una quantitativa senza introdurre ulteriore struttura sui dati.

Svolgimento. Altezza, età e velocità sono variabili numeriche; la variabile qualitativa è il colore, che assume valori in un insieme finito di concetti privi di ordine naturale.

Per la conversione si possono considerare tre candidati:

1. Codifica RGB: ogni colore diventa la terna dei suoi valori rosso/verde/blu.
2. Interi progressivi: al colore $c_i$ si associa l’intero $i$.
3. One-hot encoding: con $P$ colori possibili $c_1, \dots, c_P$, al colore $c_i$ si associa un vettore binario di lunghezza $P$ con tutte le componenti a zero e un 1 in posizione $i$.

Per decidere serve precisare che cosa significa “struttura sui dati”: la struttura è nelle distanze tra le codifiche. Con la codifica RGB alcuni colori risultano più vicini di altri (arancione e rosso hanno terne simili): si sta imponendo una nozione di somiglianza tra le classi. Con gli interi progressivi succede lo stesso e in modo più arbitrario: $c_i$ e $c_{i+1}$ risultano più vicini di $c_i$ e $c_{i+2}$ solo per come sono stati numerati. L’unica codifica che non introduce alcuna struttura è la one-hot: i vettori della base canonica di $\mathbb{R}^P$ sono tutti alla stessa distanza reciproca, quindi nessuna coppia di colori è resa più simile di un’altra.

Vale la pena notare il compromesso: le codifiche compatte (interi, RGB) usano molti meno bit, ma pagano la compattezza con un bias di somiglianza che può essere innocuo per alcuni problemi e dannoso per altri; la one-hot è neutrale ma costa $P$ dimensioni. Questa è anche la ragione per cui la codifica 1-of-K è lo standard per i target multiclasse.

10.2 Logistic regression in pratica: predire un bonus#

Traccia. Si raccolgono, per un gruppo di lavoratori, le ore lavorate $x_1$, il numero di progetti completati $x_2$ e il fatto di aver ricevuto un bonus ($t = 1$) oppure no ($t = 0$). Si addestra una logistic regression e si ottengono i coefficienti $w_0 = -6$, $w_1 = 0.05$, $w_2 = 1$.

1. Stimare la probabilità che un lavoratore con 40 ore lavorate e 3.5 progetti completati riceva il bonus.
2. Quante ore dovrebbe lavorare (a parità di progetti) per avere il 50% di probabilità di ricevere il bonus?
3. Ha senso, in questo problema, considerare valori dell’argomento della sigmoide inferiori a $-6$?

Svolgimento.

Punto 1. Il modello è $p(t = 1 \mid x_1, x_2) = \sigma(w_0 + w_1 x_1 + w_2 x_2)$: basta inserire i numeri nell’argomento della sigmoide:

$$z = -6 + 0.05 \cdot 40 + 1 \cdot 3.5 = -6 + 2 + 3.5 = -0.5$$

quindi la probabilità è $\sigma(-0.5) \approx 0.3775$: circa il 38% di probabilità di ricevere il bonus. (All’esame, se serve il valore numerico della sigmoide, viene fornita una tabellina: non va imparata a memoria.)

Punto 2. Probabilità del 50% significa $\sigma(z) = 1/2$, che accade esattamente quando l’argomento è nullo: si sta chiedendo quando il punto finisce sulla decision surface. Si risolve quindi

$$w_0 + w_1 x_1 + w_2 x_2 = 0 \quad\Longrightarrow\quad -6 + 0.05\, x_1 + 3.5 = 0 \quad\Longrightarrow\quad x_1 = \frac{2.5}{0.05} = 50$$

Servono 50 ore lavorate. Il punto concettuale da ricordare: probabilità predetta pari a $1/2$ equivale a trovarsi sul decision boundary, cioè ad argomento della sigmoide uguale a zero.

Punto 3. No. Le variabili del problema non possono essere negative ($x_1$ sono ore lavorate, $x_2$ progetti completati, entrambe $\geq 0$) e i coefficienti $w_1, w_2$ sono positivi, quindi l’argomento $z = w_0 + w_1 x_1 + w_2 x_2$ è minimo quando $x_1 = x_2 = 0$ e vale $w_0 = -6$. Valori di $z$ sotto $-6$ non corrispondono ad alcun input ammissibile del problema.

10.3 Alzare la soglia di classificazione#

Traccia. Si è addestrata una logistic regression su un dataset $Z = \{(\mathbf{x}_n, t_n)\}$; l’output sul punto $\mathbf{x}$ è $y(\mathbf{x}) \in [0, 1]$. Per trasformare il modello probabilistico in un classificatore si usa una soglia $\tau$: si predice classe 1 se $y(\mathbf{x}) > \tau$, classe 0 altrimenti. Il classificatore $L_1$ usa la soglia standard $\tau = 0.5$; il classificatore $L_2$ usa $\tau = 0.8$. Dire, motivando, quali delle seguenti affermazioni sono vere:

1. il numero di campioni di $Z$ classificati positivi diminuisce usando $L_2$ al posto di $L_1$;
2. il numero di campioni di un test set (dati nuovi) classificati positivi diminuisce usando $L_2$ al posto di $L_1$;
3. l’accuracy su $Z$ migliora usando $L_2$;
4. l’errore di classificazione su $Z$ diminuisce usando $L_2$.

Svolgimento.

Affermazione 1: vera. La regola “positivo se $y(\mathbf{x}) > \tau$” diventa più severa alzando $\tau$: l’insieme dei punti con $y > 0.8$ è un sottoinsieme di quelli con $y > 0.5$, quindi i positivi predetti non possono che diminuire (o al più restare invariati). Il caso estremo aiuta l’intuizione: con $\tau = 1$ nessun punto verrebbe classificato positivo, perché la sigmoide vale 1 solo con argomento infinito.

Affermazione 2: vera. L’argomento del punto 1 non usa da nessuna parte il fatto che i dati siano quelli di training: per qualunque insieme di punti, i positivi secondo la soglia 0.8 sono un sottoinsieme dei positivi secondo la soglia 0.5. La proprietà è del classificatore, non del dataset.

Affermazione 3: falsa (nel senso che non si può concludere nulla). Alzare la soglia trasforma alcuni positivi predetti in negativi predetti: se quei punti erano falsi positivi l’accuracy sale, se erano veri positivi scende. Senza informazioni sulla distribuzione dei dati non c’è alcuna direzione garantita. Si noti anche l’argomento di principio: il modello è stato addestrato minimizzando la cross-entropy, non massimizzando l’accuracy; non c’è quindi alcun motivo per cui la soglia 0.5 debba essere ottimale per l’accuracy, né per cui spostarla debba peggiorarla o migliorarla sistematicamente.

Affermazione 4: falsa, per la stessa ragione. L’errore di classificazione è semplicemente $1 - \text{accuracy}$: se non si può dire nulla sull’accuracy, non si può dire nulla nemmeno sull’errore. In questo tipo di domande la cosa importante non è indovinare il vero/falso ma la motivazione: la risposta corretta è “non è determinabile con le informazioni date”, e va argomentata.

Esercizio ulteriore consigliato: ragionare su come cambiano precision e recall alzando la soglia. (Traccia della risposta: meno positivi predetti significa in generale precision che tende a salire, perché si tengono solo i positivi più sicuri, e recall che tende a scendere, perché qualche positivo vero viene perso.)

10.4 Parametrico o non parametrico? Cinque scenari#

Traccia. Per ciascuna delle seguenti caratteristiche di un problema di machine learning, dire se orienta verso un metodo parametrico o non parametrico, motivando: (1) scenario big data; (2) sistema embedded; (3) disponibilità di informazione a priori sulla distribuzione dei dati; (4) apprendimento in tempo reale su dati in streaming; (5) capacità computazionali ridotte.

Svolgimento. Il criterio guida è sempre lo stesso: un metodo parametrico paga un addestramento (anche costoso) in cambio di un modello compatto e di predizioni veloci e indipendenti dalla mole di dati; un metodo non parametrico non paga alcun addestramento ma deve conservare l’intero dataset e consultarlo a ogni predizione.

1. Big data: parametrico. Con un dataset enorme, un metodo non parametrico dovrebbe tenere tutti i dati in memoria e, per ogni predizione, calcolare distanze rispetto a tutti i punti: costi di memoria e di calcolo che crescono con $N$. Un metodo parametrico condensa il dataset in pochi parametri e poi ne fa a meno.
2. Sistema embedded: dipende dal vincolo. Se il vincolo è la memoria, meglio un parametrico: tenere l’intero dataset su un dispositivo embedded è problematico, mentre un modello compatto (magari addestrato altrove e solo dispiegato sul dispositivo) occupa pochissimo. Se però l’addestramento deve avvenire sul dispositivo e il vincolo è la potenza di calcolo, il non parametrico ha il vantaggio di non richiedere alcun addestramento. La risposta giusta all’esame è articolare i due casi.
3. Informazione a priori disponibile: parametrico. Avendo parametri espliciti, un metodo parametrico permette di codificare la conoscenza a priori come distribuzione sui parametri stessi (si pensi al prior della regressione bayesiana), riducendo la quantità di dati necessaria. In un metodo non parametrico non c’è un posto naturale dove inserire questa informazione.
4. Tempo reale / streaming: parametrico. Se i dati arrivano in flusso e ogni predizione deve essere pronta prima del punto successivo, il non parametrico è in difficoltà: il dataset cresce nel tempo e ogni predizione richiede di scorrerlo tutto. Il parametrico predice in tempo costante e può aggiornarsi online (per esempio con il gradient descent stocastica). Alternativa accettabile se motivata: un non parametrico modificato che conserva solo una finestra dei dati più recenti, eliminando la dipendenza da $N$.
5. Capacità computazionali ridotte: dipende dalla fase. Se il collo di bottiglia è l’addestramento, il non parametrico vince perché non si addestra affatto; se il collo di bottiglia è la predizione, vince il parametrico perché predire costa pochissimo. Come nel punto 2, la risposta completa distingue i due casi.

Osservazione generale valida per tutto questo tipo di domande: raramente esiste un’unica risposta “giusta”; ciò che viene valutato è la qualità della motivazione, cioè la capacità di collegare i vincoli dello scenario alle proprietà strutturali (memoria, costo di training, costo di predizione, uso di conoscenza a priori) delle due famiglie di metodi.

Glossario#

Dispensa Machine Learning · Politecnico di Milano